package com.hyper_yang.algorithmRecord;

// leetcode 55 跳跃游戏
public class LeetCode_55 {
    // 给你一个非负整数数组 nums，你最初位于数组的第一个下标 。
// 数组中的每个元素代表你在该位置可以跳跃的最大长度。
//判断你是否能够到达最后一个下标，如果可以，返回 true；否则，返回 false。
    // 方法一: 贪心实现
    public static boolean canJump(int[] nums) {
        // 保存当前能跳到的最远距离
        int farthest = 0;
        // 更新 farthest
        for (int i = 0; i < nums.length; i++) {
            // 下一个位置 i，要处于 farthest能到达的位置
            if (i <= farthest) {
                farthest = Math.max(farthest, i + nums[i]);
                if (farthest >= nums.length - 1) return true;
            } else return false;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(canJump(new int[]{2, 3, 1, 1, 4}));
        System.out.println(canJump(new int[]{3, 2, 1, 0, 4}));
    }
}
